[NOIP2019]划分

2019-12-12
#动态规划Dp #单调队列
NOIP

题意

给出$\{a_i\}$，求$\{p_k\}$，使得

求

的最小值

题解

先给出$\theta(n^3)​$Dp，令$f_{i,j}​$表示只考虑前i个数，前一个p=j的最小值

固定j，单调地取k，可以优化到$\theta(n^2)​$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
const int maxn = 5005;
const LL INF = 0x3f3f3f3f3f3f3f3f;
using namespace std;
LL f[maxn][maxn], s[maxn], a[maxn];
int n, type;
int main(){
	scanf("%d%d", &n, &type);
	for (int i = 1; i <= n; i++) scanf("%d", a + i), s[i] = s[i - 1] + a[i];
	memset(f, 0x3f, sizeof f);
	for (int i = 1; i <= n; i++) f[i][0] = s[i] * s[i]; 
	for (int j = 1; j < n; j++){
		int k = j; LL Min = INF;
		for (int i = j + 1; i <= n; i++){
			while (s[i] - s[j] >= s[j] - s[k - 1] && k > 0) Min = min(Min, f[j][--k]);
			f[i][j] = min(f[i][j], Min + (s[i] - s[j]) * (s[i] - s[j]));
		}
	}
	LL ans = INF;
	for (int i = 0; i <= n; i++) ans = min(ans, f[n][i]);
	printf("%lld\n", ans);
	return 0;
}

容易证明，最后一部分越小越优，令$d_i$为以i结尾的最优方案时最后一段的大小

每次$f_i$自然是由满足$d_j\leq s_i-s_j$，即$d_j+s_j\leq s_i​$中最大的j转移而来（这个结论不大会证，但是举不出反例呵呵呵）

若$j>k$，且$d_k+s_k>d_j+s_j$，那么k就是无效的，维护关于$d_j+s_j$的单调队列即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
const int maxn = 4e7 + 10;
using namespace std;
LL f[maxn], s[maxn], a[maxn], d[maxn];
int n, type, l, r, q[maxn];
int main(){
	scanf("%d%d", &n, &type);
	for (int i = 1; i <= n; i++) scanf("%d", a + i), s[i] = s[i - 1] + a[i];
	q[l = r = 0] = 0;
	for (int i = 1; i <= n; i++){
		while (l < r && d[q[l + 1]] + s[q[l + 1]] <= s[i]) ++l;
		d[i] = s[i] - s[q[l]]; f[i] = f[q[l]] + d[i] * d[i];
		while (l < r && d[q[r]] + s[q[r]] >= d[i] + s[i]) --r;
		q[++r] = i;
	} printf("%lld\n", f[n]);
	return 0;
}